/*
 * @lc app=leetcode id=98 lang=cpp
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }
        vector<TreeNode *> path;
        TreeNode *lastmost = NULL;
        TreeNode *node = root;

        while (node || !path.empty()) {
            if (!node) {
                node = path.back();
                path.pop_back();

                if (lastmost && lastmost->val >= node->val) {
                    return false;
                }
            } else {
                while(node->left) {
                    path.push_back(node);
                    node = node->left;
                }
            }

            if (node) {
                if (lastmost) {
                    if (lastmost->val >= node->val) {
                        return false;
                    } else {
                        lastmost = node;
                    }
                } else {
                    lastmost = node;
                }
            }

            node = node->right;
        }
        return true;
    }
};

